This disclosure relates generally to the field of networked electronic devices, and more particularly to methods for determining the positions of nodes in a communications network.
For example, a network of sensors may be sprinkled across a large building or an area such as a forest. Typical tasks for such networks are to send a message to a node at a given location (without knowing which node or nodes are there, or how to get there), to retrieve sensor data (e.g., sound or temperature levels) from nodes in a given region, and to find nodes with sensor data in a given range. Most of these tasks require knowing the positions of the nodes, or at least relative positions among them. With a network of thousands of nodes, it is unlikely that the position of each node has been pre-determined. Nodes could be equipped with a global positioning system (GPS) to provide them with absolute position, but this is a costly solution.
Among existing localization methods for communications networks, one approach, suggested by L. Doherty et al., “Convex Position Estimation in Wireless Sensor Networks”, in Proc. Infocom 2001, Anchorage, Ak., April 2001, is based on connectivity only. This convex constraint satisfaction approach describes a method for localizing sensor nodes based only on connectivity. The method formulates the localization problem as a feasibility problem with convex radial constraints. The problem is in turn solved by efficient semi-definite programming (an interior point method) to find a global solution. For the case with directional communication, the method formulates the localization problem as a linear programming problem, which is solved by an interior point method. This method requires centralized computation. For the method to work well, it needs ‘anchor nodes’, whose positions are already known, to be placed on the outer boundary, preferably at the corners. Only in this configuration are the constraints tight enough to yield a useful configuration. When all anchors are located in the interior of the network, the position estimation of outer nodes can easily collapse toward the center, which leads to large estimation errors. For example, with 10% anchors, the error of unknowns is on the order of the radio range. With 5 anchors in a 200-node random network, the error of unknowns is more than twice the radio range.
Most localization methods for ad-hoc networks require more information than just connectivity and use more powerful beacon nodes. The ad-hoc localization techniques used in mobile robots usually fall into this category and are described in A. Howard, et al., “Relaxation on a Mesh: A Formalism for Generalized Localization”, in Proc. IEEE/RSJ Int'l Conf. On Intelligent Robots and Systems (IROS-01), pages 1055-1060, 2001. Mobile robots use additional odometric measurements for estimating the initial robot positions, which are not available in sensor networks.
Many existing localization techniques for networks use distance or angle measurements from a fixed set of reference points or anchor nodes and apply multilateration or triangulation techniques to find coordinates of unknown nodes, as in A. Nasipuri and K. Li, “A Directionality Based Location Discovery Scheme for Wireless Sensor Networks”, in 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications (WSNA '02), pages 105-111, Atlanta, Ga., September 2002. The distance estimates can be obtained from received signal strength (RSSI) or time-of-arrival (ToA) measurements. Due to non-uniform signal propagation environments, RSSI methods are not very reliable and accurate. ToA methods have better accuracy, but may require additional hardware at the nodes to receive a signal that has a smaller propagation speed than radio, such as ultrasound (A. Savvides, et al., “Dynamic fine-grained Localization in Ad Hoc Networks of Sensors”, in ACM/IEEE Int'l Conf. On Mobile Computing and Networking (MOBICON), July 2001). Emphasis has been placed on algorithms that can be executed in a distributed fashion on the nodes without centralized computation, communication, or information propagation. The “DV-based” approach suggested by D. Niculescu and B., “Ad-hoc Positioning System”, in IEEE GlobeCom, November 2001, is distributed. The “DV-hop” method achieves a location error of about 45% of the radio range for networks with 100 nodes, 5 anchors, and average connectivity 7.6. Initially, anchor nodes flood their location to all nodes in the network. Each unknown node performs a triangulation to three or more anchors to estimate its own position. This method works well in dense and regular topologies, but for sparse and irregular networks, the accuracy degrades to the radio range. The “DVdistance” method uses distance between neighboring nodes and reduces the location error by about half of that of “DV-hop”.
Savarese et al. propose another distributed method in “Robust Positioning Algorithm for Distributed Ad-hoc Wireless Sensor Networks”, in USENIX Technical Annual Conf., Monterey, Calif., June 2002. The method consists of start-up and refinement phases. For the start-up phase, Hop-TERRAIN, an algorithm similar to DV-hop, is utilized. Hop-TERRAIN, which requires at least three initial anchor nodes, is run once at the beginning to generate a rough initial estimate of the nodes' locations. Then the refinement algorithm is run iteratively to improve and refine the position estimates. The algorithm is concerned only with nodes within a one-hop neighborhood and uses a least-squares triangulation method to determine a node's position based on its neighbors' positions and distances to them. The approach can deliver localization accuracy within one third of the communication range.
When the number of anchor nodes is high, the collaborative multilateration approach by Savvides et al., “The bits and Flops of the n-hop Multilateration Primitive for Node Localization Problems”, in 1st ACM Int'l Workshop on Wireless Sensor Networks and Applications (WSNA '02), pages 112-121, Atlanta, Ga., September 2002, has been suggested. This approach estimates node locations by using anchor locations that are several hops away and distance measurements to neighboring nodes. A global nonlinear optimization problem is then solved. The method has three main phases: 1) formation of a collaborative subtree, which only includes nodes whose positions can be uniquely determined; 2) computation of initial estimates with respect to anchor nodes; and 3) position refinement by minimizing the residuals between the measured distances between the nodes and the distances computed using the node location estimates. They present both a centralized computation model and a distributed approximation of the centralized model. The method works well when the fraction of anchor nodes is high.
Most of the existing methods require anchor or beacon nodes to begin the process. It would be advantageous to have a system and approach which does not have this limitation and can construct a relative map of the network nodes even without anchor nodes, while maintaining estimation accuracy.